Search for: All records

We establish a tantalizing symmetry of certain numbers refining the Narayana numbers. In terms of Dyck paths, this symmetry is interpreted in the following way: if $$w_{n,k,m}$$ is the number of Dyck paths of semilength $$n$$ with $$k$$ occurrences of $UD$ and $$m$$ occurrences of $UUD$, then $$w_{2k+1,k,m}=w_{2k+1,k,k+1-m}$$. We give a combinatorial proof of this fact, relying on the cycle lemma, and showing that the numbers $$w_{2k+1,k,m}$$ are multiples of the Narayana numbers. We prove a more general fact establishing a relationship between the numbers $$w_{n,k,m}$$ and a family of generalized Narayana numbers due to Callan. A closed-form expression for the even more general numbers $$w_{n,k_{1},k_{2},\ldots, k_{r}}$$ counting the semilength-$$n$$ Dyck paths with $$k_{1}$$ $UD$-factors, $$k_{2}$$ $UUD$-factors, $$\ldots$$, and $$k_{r}$$ $$U^{r}D$$-factors is also obtained, as well as a more general form of the discussed symmetry for these numbers in the case when all rise runs are of certain minimal length. Finally, we investigate properties of the polynomials $$W_{n,k}(t)= \sum_{m=0}^k w_{n,k,m} t^m$$, including real-rootedness, $$\gamma$$-positivity, and a symmetric decomposition. 

Abstract Given a permutation statistic$$\operatorname {\mathrm {st}}$$, define its inverse statistic$$\operatorname {\mathrm {ist}}$$by. We give a general approach, based on the theory of symmetric functions, for finding the joint distribution of$$\operatorname {\mathrm {st}}_{1}$$and$$\operatorname {\mathrm {ist}}_{2}$$whenever$$\operatorname {\mathrm {st}}_{1}$$and$$\operatorname {\mathrm {st}}_{2}$$are descent statistics: permutation statistics that depend only on the descent composition. We apply this method to a number of descent statistics, including the descent number, the peak number, the left peak number, the number of up-down runs and the major index. Perhaps surprisingly, in many cases the polynomial giving the joint distribution of$$\operatorname {\mathrm {st}}_{1}$$and$$\operatorname {\mathrm {ist}}_{2}$$can be expressed as a simple sum involving products of the polynomials giving the (individual) distributions of$$\operatorname {\mathrm {st}}_{1}$$and$$\operatorname {\mathrm {st}}_{2}$$. Our work leads to a rederivation of Stanley’s generating function for doubly alternating permutations, as well as several conjectures concerning real-rootedness and$$\gamma $$-positivity. 

The kernel $$\mathcal{K}^{\operatorname{st}}$$ of a descent statistic $$\operatorname{st}$$, introduced by Grinberg, is a subspace of the algebra $$\operatorname{QSym}$$ of quasisymmetric functions defined in terms of $$\operatorname{st}$$-equivalent compositions, and is an ideal of $$\operatorname{QSym}$$ if and only if $$\operatorname{st}$$ is shuffle-compatible. This paper continues the study of kernels of descent statistics, with emphasis on the peak set $$\operatorname{Pk}$$ and the peak number $$\operatorname{pk}$$. The kernel $$\mathcal{K}^{\operatorname{Pk}}$$ in particular is precisely the kernel of the canonical projection from $$\operatorname{QSym}$$ to Stembridge's algebra of peak quasisymmetric functions, and is the orthogonal complement of Nyman's peak algebra. We prove necessary and sufficient conditions for obtaining spanning sets and linear bases for the kernel $$\mathcal{K}^{\operatorname{st}}$$ of any descent statistic $$\operatorname{st}$$ in terms of fundamental quasisymmetric functions, and give characterizations of $$\mathcal{K}^{\operatorname{Pk}}$$ and $$\mathcal{K}^{\operatorname{pk}}$$ in terms of the fundamental basis and the monomial basis of $$\operatorname{QSym}$$. Our results imply that the peak set and peak number statistics are $$M$$-binomial, confirming a conjecture of Grinberg. 

Abstract A permutation statistic$${{\,\textrm{st}\,}}$$ $\text{st}$is said to be shuffle-compatible if the distribution of$${{\,\textrm{st}\,}}$$ $\text{st}$over the set of shuffles of two disjoint permutations$$\pi $$ $\pi$and$$\sigma $$ $\sigma$depends only on$${{\,\textrm{st}\,}}\pi $$ $\text{st}\pi$,$${{\,\textrm{st}\,}}\sigma $$ $\text{st}\sigma$, and the lengths of$$\pi $$ $\pi$and$$\sigma $$ $\sigma$. Shuffle-compatibility is implicit in Stanley’s early work onP-partitions, and was first explicitly studied by Gessel and Zhuang, who developed an algebraic framework for shuffle-compatibility centered around their notion of the shuffle algebra of a shuffle-compatible statistic. For a family of statistics called descent statistics, these shuffle algebras are isomorphic to quotients of the algebra of quasisymmetric functions. Recently, Domagalski, Liang, Minnich, Sagan, Schmidt, and Sietsema defined a version of shuffle-compatibility for statistics on cyclic permutations, and studied cyclic shuffle-compatibility through purely combinatorial means. In this paper, we define the cyclic shuffle algebra of a cyclic shuffle-compatible statistic, and develop an algebraic framework for cyclic shuffle-compatibility in which the role of quasisymmetric functions is replaced by the cyclic quasisymmetric functions recently introduced by Adin, Gessel, Reiner, and Roichman. We use our theory to provide explicit descriptions for the cyclic shuffle algebras of various cyclic permutation statistics, which in turn gives algebraic proofs for their cyclic shuffle-compatibility.